#include <stdio.h>
#include <stdlib.h>

#define MAX 65535

typedef struct Graph{
    char *vexs;
    int **arcs;
    int vexNum;
    int arcNum;
} Graph;

//栈 首元节点data记录个数
typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *initStack() 
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = 0;
    node->next = NULL;
    return node;
}

void push(Node *S, int data) 
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = S->next;
    S->next = node;
    S->data++;
}

int isEmpty(Node *S)
{
    if (S->next == NULL || S->data == 0) return 1;
    return 0;
}

int pop(Node *S)
{   if (!isEmpty(S)) {
        Node *del = S->next;
        S->next = del->next;
        int ret = del->data;
        S->data--;
        free(del);
        return ret;
    }
    return -1;
}

Graph *initGraph(int vexNum) //顶点数
{
    Graph *G = (Graph *)malloc(sizeof(Graph));
    G->arcs = (int **)malloc(sizeof(int *) * vexNum);
    G->vexs = (char *)malloc(sizeof(char) * vexNum);
    for (int i = 0; i < vexNum; i++) {
        G->arcs[i] = (int *)malloc(sizeof(int) * vexNum);
    }
    G->arcNum = 0;
    G->vexNum = vexNum;
    return G;
}

void createGraph(Graph *G, char *vexs, int *arcs)
{
    for (int i = 0; i < G->vexNum; i++) {
        G->vexs[i] = vexs[i];
        for (int j = 0; j < G->vexNum; j++) { //注意此时只是普通的二级指针
            G->arcs[i][j] = *(arcs + i * G->vexNum + j);
            if (G->arcs[i][j] > 0 && G->arcs[i][j] != MAX) {
                G->arcNum++;
            }
        }
    }
    //G->arcNum /= 2;
}

int * findInDegress(Graph *G) 
{
    int *inDegress = (int *)malloc(sizeof(int) * G->vexNum);
    for (int j = 0; j < G->vexNum; j++) { //从列开始循环
        inDegress[j] = 0;//初始化
        for (int i = 0; i < G->vexNum; i++) {
            if (G->arcs[i][j] > 0 && G->arcs[i][j] != MAX) {//有入
                inDegress[j]++;
            }
        }
    }
    return inDegress;
}

/**
 * 初始化一个入度数组inDegess
 * 思路：可以使用尾递归的思路
 * 1. 寻找inDegress为零的点 输出 并删除从它出来的边
 * 2. 循环第一步 直到 没有入度为零的点
 * 作用：判断图中是否有环 如果有那么顶点输出不完全
*/
//使用stack避免多次循环 提高速度
int *topologicalSort(Graph *G)
{
    int *inDegress = findInDegress(G);
    Node *stack = initStack();
    for (int i = 0; i< G->vexNum; i++) { //首先入度为零入栈
        if (inDegress[i] == 0) {
            push(stack, i);
        }
    }
    //结果数组
    int *top = (int *)malloc(sizeof(int) * G->vexNum);
    int index = 0;
    while (!isEmpty(stack)) {
        int vex = pop(stack);
        top[index++] = vex;
        for (int j = 0; j < G->vexNum; j++) { 
            if (G->arcs[vex][j] > 0 && G->arcs[vex][j] != MAX) {
                inDegress[j]--;
                if (inDegress[j] == 0) {
                    push(stack, j);
                }
            }
        }
    }
    if (index < G->vexNum) printf("有环!\n");
    for (int i = 0; i < index; i++) {
        printf("%c ", G->vexs[top[i]]);
    }
    printf("\n");
    return top;
}
//返回j对应的top下标
int getIndex(int *top, Graph *G, int i)
{
    int j;
    for (j = 0; j < G->vexNum; j++) {
        if (i == top[j])
            break;
    }
    return j;
}
/** 
 * 1. 拓扑排序
 * 2. 事件指标 活动指标 分为最早发生事件和最晚发生时间
 * 3. 其中：
 *      事件:
 *        最早 = max(前面最早+weight)
 *        最晚 = min(后面最晚-weight)
 *      活动:
 *        最早 = 前一个点的最早发生时间
 *        最晚 = 后一个点的最晚-weight
 *      关键活动： 
 *      时间余量=0 即 活动的最早-最晚=0; 这也是最后代码那样写的原因
*/
void criticalPath(Graph *G)
{
    int * top = topologicalSort(G);
    int *early = (int *)malloc(sizeof(int) * G->vexNum);
    int *late = (int *)malloc(sizeof(int) * G->vexNum);
    //初始化early和late数组
    for (int i = 0; i < G->vexNum; i++) {
        early[i] = 0;
        late[i] = 0;
    }
    //计算最早发生时间
    for (int i = 0; i < G->vexNum; i++) {//从top第一个开始
        int max = 0;//找最大值
        for (int j = 0; j < G->vexNum; j++) {
            if (G->arcs[j][top[i]] > 0 && G->arcs[j][top[i]] != MAX) {//首先j->top[i]有边
                int index = getIndex(top, G, j);//获取j的索引
                if (early[index] + G->arcs[j][top[i]] > max) //从前面的点选最早发生时间加weight最大得值
                    max = early[index] + G->arcs[j][top[i]]; 
            }
        }
        early[i] = max;
    }
    for (int i = 0; i < G -> vexNum; i++) {
        printf("%d ", early[i]);
    }
    printf("\n");
    //计算最晚发生时间
    late[(G->vexNum)-1] = early[(G->vexNum)-1];
    for (int i = (G->vexNum)-2; i >= 0; i--) {
        int min = MAX;
        for (int j = 0; j < G->vexNum; j++) {
            if (G->arcs[top[i]][j] > 0 && G->arcs[top[i]][j] != MAX) {
                int index = getIndex(top, G, j);
                if (late[index] - G->arcs[top[i]][j] < min)
                    min = late[index] - G->arcs[top[i]][j];
        }
        late[i] = min;
        }
    }
    for (int i = 0; i < G -> vexNum; i++) {
        printf("%d ", late[i]);
    }
    putchar('\n');
    //计算时间余量
    for (int i = 0; i < G->vexNum; i++) {
        for (int j = 0; j < G->vexNum; j++) {
            if (G->arcs[i][j] > 0 && G->arcs[i][j] != MAX) {
                int start = getIndex(top, G, i);
                int end   = getIndex(top, G, j);
                if (early[start] == late[end] - G->arcs[i][j])
                    printf("start=%d end=%d\n", i, j);
            }
        }
    }
}
void DFS(Graph *G, int *visited, int index) //索引第一个节点开始
{
    printf("%c ", G->vexs[index]);//访问
    visited[index] = 1;
    for (int i = 0; i < G->vexNum; i++) {
        if (G->arcs[index][i] > 0 && G-> arcs[index][i] != MAX && !visited[i]) {//遍历 + 递归
            DFS(G, visited, i);
        }
    }
}

int main(void)
{
    Graph* G = initGraph(9);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (int i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    int arcs[9][9] = {
        0, 6, 4, 5, MAX, MAX, MAX, MAX, MAX,
        MAX, 0, MAX, MAX, 1, MAX, MAX, MAX, MAX,
        MAX, MAX, 0, MAX, 1, MAX, MAX, MAX, MAX,
        MAX, MAX, MAX, 0, MAX, 2, MAX, MAX, MAX,
        MAX, MAX, MAX, MAX, 0, MAX, 9, 7, MAX,
        MAX, MAX, MAX, MAX, MAX, 0, MAX, 4, MAX,
        MAX, MAX, MAX, MAX, MAX, MAX, 0, MAX, 2,
        MAX, MAX, MAX, MAX, MAX, MAX, MAX, 0, 4,
        MAX, MAX, MAX, MAX, MAX, MAX, MAX, MAX, 0
    };
    createGraph(G, "012345678", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
    criticalPath(G);
    return 0;
}